package Java1Test;

import utils.PrintArr;

import java.util.Random;

public class LeetCodeQuickSort {
    private static final Random random = new Random();

    public static void main(String[] args) {
        int[] nums = {5, 2, 3, 1};
        sortArray(nums);
        PrintArr.printArr(nums); // 输出排序后的数组
    }

    /**
     * 对数组进行排序（入口方法）
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public static int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums; // 空数组或长度为1直接返回
        }
        quickSort1(nums, 0, nums.length - 1); // 调用快速排序
        return nums;
    }

    /**
     * 快速排序实现（递归法）
     * @param nums 待排序数组
     * @param left 当前分区左边界
     * @param right 当前分区右边界
     */
    public static void quickSort1(int[] nums, int left, int right) {
        if (left >= right) {
            return; // 递归终止条件：分区大小<=1
        }

        // 随机选择基准数并交换到左边界
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);

        int start = left; // 左指针
        int end = right;  // 右指针
        int baseNumber = nums[left]; // 基准数

        // 双指针遍历分区
        while (start < end) {
            // 从右向左找第一个小于基准数的元素
            while (end > start && nums[end] >= baseNumber) {
                end--;
            }
            // 从左向右找第一个大于基准数的元素
            while (end > start && nums[start] <= baseNumber) {
                start++;
            }

            if (end > start) {
                swap(nums, start, end); // 交换左右指针元素
            }
        }

        // 将基准数放到正确位置
        swap(nums, left, start);

        // 递归排序左右子分区
        quickSort1(nums, left, start - 1);
        quickSort1(nums, start + 1, right);
    }

    /**
     * 交换数组中两个元素的位置
     * @param nums 数组
     * @param i 索引i
     * @param j 索引j
     */
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}